// url: https://leetcode.cn/problems/jump-game/?envType=study-plan-v2&envId=top-interview-150
package interview_classic.array_or_str;

public class Solution55 {
    public static void main(String[] args) {
        int[] arr = {2,3,1,1,4};
        System.out.println(canJump(arr));
    }
    // way2 贪心？ 没学过 学完贪心后在看


    // 自己写的
    public static boolean canJump(int[] nums) {
        int curIndex = 0;
        while (curIndex < nums.length) {
            boolean flag = false;
            int i = curIndex + 1;
            // 这个应该从后往前 这样速度可以快一些 ？
            // 经过实践 发现如果像 3 0 8 2 0 0 1 这类（前面和后面都满足条件 但是前面范围更大）就不适合从后往前
            for (; i <= nums[curIndex] + curIndex && i < nums.length; i++) {
                int gap = i - curIndex; // gap >= 1
                if (nums[curIndex] - gap < nums[i]) {
                    curIndex = i;
                    flag = true;
                    break;
                }
            }
            // 没有进入： 1. 没找到 2. i 越界
            if (!flag) return i == nums.length;
        }
        return true;
    }
}
